package com.hyc.DataStructure.tree.ThreadedBinaryTree;

/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.tree.ThreadedBinaryTree
 * @className: ThreadedBinaryTreeDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/5 16:38
 * @version: 1.0
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        //测试一把中序线索二叉树的功能
        heroNode root = new heroNode(1, "tom");
        heroNode node2 = new heroNode(3, "jack");
        heroNode node3 = new heroNode(6, "smith");
        heroNode node4 = new heroNode(8, "mary");
        heroNode node5 = new heroNode(10, "king");
        heroNode node6 = new heroNode(14, "dim");

        //二叉树，后面我们要递归创建, 现在简单处理使用手动创建
        root.setLeftNode(node2);
        root.setRightNode(node3);
        node2.setLeftNode(node4);
        node2.setRightNode(node5);
        node3.setLeftNode(node6);

        //测试中序线索化
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setHead(root);
        threadedBinaryTree.postThreadedNodes(root);

        //测试: 以10号节点测试
        heroNode leftNode = node5.getLeftNode();
        heroNode rightNode = node5.getRightNode();
        System.out.println("10号结点的前驱结点是 =" + leftNode); //3
        System.out.println("10号结点的后继结点是=" + rightNode); //1

        //当线索化二叉树后，能在使用原来的遍历方法
        //threadedBinaryTree.infixOrder();
        System.out.println("使用线索化的方式遍历 线索化二叉树");
        threadedBinaryTree.preThreaddeList(); // 8, 3, 10, 1, 14, 6

    }

}

class ThreadedBinaryTree {
    //确定根节点
    private heroNode head;
    //递归的时候用来存放上一个节点的变量用于线索化树的遍历和线索化节点
    private heroNode pre;

    public void setHead(heroNode head) {
        this.head = head;
    }

    //线索化遍历
    public void ThreaddeList() {
        //    这里我们需要一个变量，存储当前的节点
        heroNode tempNode = head;
        while (tempNode != null) {
            /* 开始循环遍历
             * 循环找到 lefttype 为 1 的节点来，所以第一个找到的就是节点值为 8 的节点
             * 后面会随着遍历而变化，当找到了 lefttype ==1的时候 说明树已经线索化了
             * 之后只需要处理线索化之后的有效节点即可
             * */
            while (tempNode.getLefttype() == 0) {
                tempNode = tempNode.getLeftNode();
            }
            //    因为是中序遍历， 顺序为 ： 左 中 右 这里我们是从左边的lefttype==1也就是说是左边开头的第一个节点所以直接输出就可以了
            System.out.println(tempNode);
            /* 如果当前节点的右指针指向的是后继节点那么就一直输出
             * */
            while (tempNode.getRighttype() == 1) {
                tempNode = tempNode.getRightNode();
                System.out.println(tempNode);
            }
            // 替换这个遍历的节点
            tempNode = tempNode.getRightNode();
        }
    }

    public void preThreaddeList() {
        //    这里我们需要一个变量，存储当前的节点
        heroNode tempNode = head;
        while (tempNode != null) {
            /* 开始循环遍历
             * 循环找到 lefttype 为 1 的节点来，所以第一个找到的就是节点值为 8 的节点
             * 后面会随着遍历而变化，当找到了 lefttype ==1的时候 说明树已经线索化了
             * 之后只需要处理线索化之后的有效节点即可
             * */
            while (tempNode.getLefttype() == 0) {
                System.out.println(tempNode);
                tempNode = tempNode.getLeftNode();
            }
            //    因为是中序遍历， 顺序为 ： 左 中 右 这里我们是从左边的lefttype==1也就是说是左边开头的第一个节点所以直接输出就可以了
            System.out.println(tempNode);
            // 替换这个遍历的节点
            tempNode = tempNode.getRightNode();
        }


    }
    
    //线索化节点
    public void ThreadedNodes(heroNode node) {
        //       非空判断
        if (node == null) {
            return;
        }
        //    线索化左子树
        ThreadedNodes(node.getLeftNode());
        //    线索化节点
        //不太好理解这里以 8 举例子
        // 8 的left ==null 那么 8 的lefttype = 1 代表他是一个前驱节点
        if (node.getLeftNode() == null) {
            //如果当前节点的左指针是空值那么就将她的left指针指向pre前置节点
            //以8为例子那么当第一次进入方法 pre 是空的 所以 8 是没有前置节点的，自己便是前置节点，所以左指针状态为1
            node.setLeftNode(pre);
            //    指向之后 将type改变为1
            node.setLefttype(1);
        }
        //处理后继节点
        //这里判断的前置节点非空并且前置节点没有后继结点
        if (pre != null && pre.getRightNode() == null) {
            //这里以8 的后一个节点为例子 3当指针指向3 的时候前置节点 pre  = 8这里指向的意思是 8 的rightnode为3
            pre.setRightNode(node);
            //此时后置节点不是子树，并且前置节点的right指针指向了node的时候 改变right 状态 为 1表示为后继节点
            pre.setRighttype(1);
        }

        //每次处理了一个节点之后，我们都需要将他存储到pre也就是前置节点中
        //否则会造成死递归
        pre = node;
        //    线索化右子树
        ThreadedNodes(node.getRightNode());

    }

    //线索化节点
    public void preThreadedNodes(heroNode node) {
        //       非空判断
        if (node == null) {
            return;
        }

        //    线索化节点
        //不太好理解这里以 8 举例子
        // 8 的left ==null 那么 8 的lefttype = 1 代表他是一个前驱节点
        if (node.getLeftNode() == null) {
            //如果当前节点的左指针是空值那么就将她的left指针指向pre前置节点
            //以8为例子那么当第一次进入方法 pre 是空的 所以 8 是没有前置节点的，自己便是前置节点，所以左指针状态为1
            node.setLeftNode(pre);
            //    指向之后 将type改变为1
            node.setLefttype(1);
        }
        //处理后继节点
        //这里判断的前置节点非空并且前置节点没有后继结点
        if (pre != null && pre.getRightNode() == null) {
            //这里以8 的后一个节点为例子 3当指针指向3 的时候前置节点 pre  = 8这里指向的意思是 8 的rightnode为3
            pre.setRightNode(node);
            //此时后置节点不是子树，并且前置节点的right指针指向了node的时候 改变right 状态 为 1表示为后继节点
            pre.setRighttype(1);
        }

        //每次处理了一个节点之后，我们都需要将他存储到pre也就是前置节点中
        //否则会造成死递归
        pre = node;
        if (node.getLefttype() == 0) {
            //    线索化左子树
            preThreadedNodes(node.getLeftNode());
        }
        if (node.getRighttype() == 0) {
            //    线索化右子树
            preThreadedNodes(node.getRightNode());
        }
    }

    //线索化节点
    public void postThreadedNodes(heroNode node) {
        //       非空判断
        if (node == null) {
            return;
        }
        //    线索化左子树
        ThreadedNodes(node.getLeftNode());
        //    线索化右子树
        ThreadedNodes(node.getRightNode());
        //    线索化节点
        //不太好理解这里以 8 举例子
        // 8 的left ==null 那么 8 的lefttype = 1 代表他是一个前驱节点
        if (node.getLeftNode() == null) {
            //如果当前节点的左指针是空值那么就将她的left指针指向pre前置节点
            //以8为例子那么当第一次进入方法 pre 是空的 所以 8 是没有前置节点的，自己便是前置节点，所以左指针状态为1
            node.setLeftNode(pre);
            //    指向之后 将type改变为1
            node.setLefttype(1);
        }
        //处理后继节点
        //这里判断的前置节点非空并且前置节点没有后继结点
        if (pre != null && pre.getRightNode() == null) {
            //这里以8 的后一个节点为例子 3当指针指向3 的时候前置节点 pre  = 8这里指向的意思是 8 的rightnode为3
            pre.setRightNode(node);
            //此时后置节点不是子树，并且前置节点的right指针指向了node的时候 改变right 状态 为 1表示为后继节点
            pre.setRighttype(1);
        }

        //每次处理了一个节点之后，我们都需要将他存储到pre也就是前置节点中
        //否则会造成死递归
        pre = node;


    }

    //   前序遍历
    public void preOrder() {
        if (this.head != null) {
            this.head.PreOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }

    //中序遍历
    public void InfixOrder() {
        if (this.head != null) {
            this.head.infixOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }

    //后续遍历
    public void PostOrder() {
        if (this.head != null) {
            this.head.postOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }

    //前序查找
    public heroNode preOrderSearch(int no) {
        if (this.head != null) {
            return this.head.PreOrderSearch(no);
        } else {
            return null;
        }
    }

    //中序查找
    public heroNode infixOrderSearch(int no) {
        if (this.head != null) {
            return this.head.infixOrderSearch(no);
        } else {
            return null;
        }
    }

    //后序查找
    public heroNode postOrderSearch(int no) {
        if (this.head != null) {
            return this.head.postOrderSearch(no);
        } else {
            return null;
        }
    }


    //    删除节点
    public void deleteNode(int no) {
        if (head != null) {
            if (head.getId() == no) {
                head = null;
                return;
            } else {
                head.deleteNode(no);
            }
        } else {
            System.out.println("空树,无法删除");
        }
    }
}

class heroNode {
    private int id;
    private String name;
    private heroNode leftNode;
    private heroNode rightNode;
    //如果type 为 0 那么代表还有子树，如果type为1代表是前驱节点/后置节点
    private int lefttype;
    private int righttype;

    public int getLefttype() {
        return lefttype;
    }

    public void setLefttype(int lefttype) {
        this.lefttype = lefttype;
    }

    public int getRighttype() {
        return righttype;
    }

    public void setRighttype(int righttype) {
        this.righttype = righttype;
    }

    public heroNode getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(heroNode leftNode) {
        this.leftNode = leftNode;
    }

    public heroNode getRightNode() {
        return rightNode;
    }

    public void setRightNode(heroNode rightNode) {
        this.rightNode = rightNode;
    }

    public heroNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    @Override
    public String toString() {
        return "heroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    public void setName(String name) {
        this.name = name;

    }

    //    前序遍历
    public void PreOrder() {
        System.out.println(this);
        if (this.getLeftNode() != null) {
            this.leftNode.PreOrder();
        }
        if (this.getRightNode() != null) {
            this.rightNode.PreOrder();
        }
    }

    //    中序遍历
    public void infixOrder() {
        if (this.leftNode != null) {
            this.leftNode.infixOrder();
        }
        System.out.println(this);
        if (this.rightNode != null) {
            this.rightNode.infixOrder();
        }
    }

    //   后序遍历
    public void postOrder() {
        if (this.leftNode != null) {
            this.leftNode.postOrder();
        }
        if (this.rightNode != null) {
            this.rightNode.postOrder();
        }
        System.out.println(this);
    }

    //   前序查找
    public heroNode PreOrderSearch(int no) {
        System.out.println("前序查找");
        //比较当前节点的no 是不是我们要搜索的
        if (this.id == no) {
            return this;
        }
        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归前序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.PreOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归前序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.PreOrderSearch(no);
        }
        return resNode;
    }

    //   中序查找
    public heroNode infixOrderSearch(int no) {

        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归中序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.infixOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //比较当前节点的no 是不是我们要搜索的
        System.out.println("中序查找");
        if (this.id == no) {
            return this;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归中序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.infixOrderSearch(no);
        }
        return resNode;
    }

    //   后序查找
    public heroNode postOrderSearch(int no) {

        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归后序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.postOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归后序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.postOrderSearch(no);
        }
        //如果不为null 那么代表右边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        System.out.println("后序查找");
        //左右子树，都没有找到，那么就比较当前节点的no 是不是我们要搜索的
        if (this.id == no) {
            return this;
        }
        return resNode;
    }


    //    删除
    public void deleteNode(int no) {
        //    向左边遍历 如果左边子树有点话就将左边子树置空，如果不是就遍历右边
        if (this.leftNode != null && this.leftNode.id == no) {
            this.leftNode = null;
            return;
        }
        //    向右边遍历 如果右边子树有点话就将左边子树置空，如果左右都没有那么就绪要递归的删除
        if (this.rightNode != null && this.rightNode.id == no) {
            this.rightNode = null;
            return;
        }
        //    如果上面两步都不成功那么我们先向左边递归删除
        if (this.leftNode != null) {
            this.leftNode.deleteNode(no);
        }

        //    如果递归删除左子树也没有成功删除，那么就递归删除右边子树
        if (this.rightNode != null) {
            this.rightNode.deleteNode(no);
        }
    }
}
